The Complexity of Probabilistic Lobbying
Identifieur interne : 000E18 ( Main/Exploration ); précédent : 000E17; suivant : 000E19The Complexity of Probabilistic Lobbying
Auteurs : Gábor Erdélyi [Allemagne] ; Henning Fernau [Allemagne] ; Judy Goldsmith [États-Unis] ; Nicholas Mattei [États-Unis] ; Daniel Raible [Allemagne] ; Jörg Rothe [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2009.
Abstract
Abstract: We propose various models for lobbying in a probabilistic environment, in which an actor (called “The Lobby”) seeks to influence the voters’ preferences of voting for or against multiple issues when the voters’ preferences are represented in terms of probabilities. In particular, we provide two evaluation criteria and three bribery methods to formally describe these models, and we consider the resulting forms of lobbying with and without issue weighting. We provide a formal analysis for these problems of lobbying in a stochastic environment, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria. Specifically, we show that some of these problems can be solved in polynomial time, some are NP-complete but fixed-parameter tractable, and some are W[2]-complete. Finally, we provide (in)approximability results.
Url:
DOI: 10.1007/978-3-642-04428-1_8
Affiliations:
- Allemagne, États-Unis
- District de Düsseldorf, Kentucky, Rhénanie-Palatinat, Rhénanie-du-Nord-Westphalie
- Düsseldorf, Trèves (Allemagne)
- Université de Trèves
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001A47
- to stream Istex, to step Curation: 001930
- to stream Istex, to step Checkpoint: 000365
- to stream Main, to step Merge: 000E92
- to stream Main, to step Curation: 000E18
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct:series"><teiHeader><fileDesc><titleStmt><title xml:lang="en">The Complexity of Probabilistic Lobbying</title><author><name sortKey="Erdelyi, Gabor" sort="Erdelyi, Gabor" uniqKey="Erdelyi G" first="Gábor" last="Erdélyi">Gábor Erdélyi</name></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation><country>Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Goldsmith, Judy" sort="Goldsmith, Judy" uniqKey="Goldsmith J" first="Judy" last="Goldsmith">Judy Goldsmith</name></author><author><name sortKey="Mattei, Nicholas" sort="Mattei, Nicholas" uniqKey="Mattei N" first="Nicholas" last="Mattei">Nicholas Mattei</name></author><author><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name></author><author><name sortKey="Rothe, Jorg" sort="Rothe, Jorg" uniqKey="Rothe J" first="Jörg" last="Rothe">Jörg Rothe</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:1BCC5806382BABE9671E5E117FAEB15D32AF2F1E</idno><date when="2009" year="2009">2009</date><idno type="doi">10.1007/978-3-642-04428-1_8</idno><idno type="url">https://api.istex.fr/document/1BCC5806382BABE9671E5E117FAEB15D32AF2F1E/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001A47</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001A47</idno><idno type="wicri:Area/Istex/Curation">001930</idno><idno type="wicri:Area/Istex/Checkpoint">000365</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000365</idno><idno type="wicri:doubleKey">0302-9743:2009:Erdelyi G:the:complexity:of</idno><idno type="wicri:Area/Main/Merge">000E92</idno><idno type="wicri:Area/Main/Curation">000E18</idno><idno type="wicri:Area/Main/Exploration">000E18</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">The Complexity of Probabilistic Lobbying</title><author><name sortKey="Erdelyi, Gabor" sort="Erdelyi, Gabor" uniqKey="Erdelyi G" first="Gábor" last="Erdélyi">Gábor Erdélyi</name><affiliation wicri:level="3"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Institut für Informatik, Universität Düsseldorf, 40225, Düsseldorf</wicri:regionArea><placeName><region type="land" nuts="1">Rhénanie-du-Nord-Westphalie</region><region type="district" nuts="2">District de Düsseldorf</region><settlement type="city">Düsseldorf</settlement></placeName></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 4—Abteilung Informatik, Universität Trier, 54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Goldsmith, Judy" sort="Goldsmith, Judy" uniqKey="Goldsmith J" first="Judy" last="Goldsmith">Judy Goldsmith</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science, University of Kentucky, 40506, Lexington, KY</wicri:regionArea><placeName><region type="state">Kentucky</region></placeName></affiliation></author><author><name sortKey="Mattei, Nicholas" sort="Mattei, Nicholas" uniqKey="Mattei N" first="Nicholas" last="Mattei">Nicholas Mattei</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science, University of Kentucky, 40506, Lexington, KY</wicri:regionArea><placeName><region type="state">Kentucky</region></placeName></affiliation></author><author><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 4—Abteilung Informatik, Universität Trier, 54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation></author><author><name sortKey="Rothe, Jorg" sort="Rothe, Jorg" uniqKey="Rothe J" first="Jörg" last="Rothe">Jörg Rothe</name><affiliation wicri:level="3"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Institut für Informatik, Universität Düsseldorf, 40225, Düsseldorf</wicri:regionArea><placeName><region type="land" nuts="1">Rhénanie-du-Nord-Westphalie</region><region type="district" nuts="2">District de Düsseldorf</region><settlement type="city">Düsseldorf</settlement></placeName></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2009</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">1BCC5806382BABE9671E5E117FAEB15D32AF2F1E</idno><idno type="DOI">10.1007/978-3-642-04428-1_8</idno><idno type="ChapterID">8</idno><idno type="ChapterID">Chap8</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We propose various models for lobbying in a probabilistic environment, in which an actor (called “The Lobby”) seeks to influence the voters’ preferences of voting for or against multiple issues when the voters’ preferences are represented in terms of probabilities. In particular, we provide two evaluation criteria and three bribery methods to formally describe these models, and we consider the resulting forms of lobbying with and without issue weighting. We provide a formal analysis for these problems of lobbying in a stochastic environment, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria. Specifically, we show that some of these problems can be solved in polynomial time, some are NP-complete but fixed-parameter tractable, and some are W[2]-complete. Finally, we provide (in)approximability results.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>États-Unis</li></country><region><li>District de Düsseldorf</li><li>Kentucky</li><li>Rhénanie-Palatinat</li><li>Rhénanie-du-Nord-Westphalie</li></region><settlement><li>Düsseldorf</li><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><country name="Allemagne"><region name="Rhénanie-du-Nord-Westphalie"><name sortKey="Erdelyi, Gabor" sort="Erdelyi, Gabor" uniqKey="Erdelyi G" first="Gábor" last="Erdélyi">Gábor Erdélyi</name></region><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name><name sortKey="Rothe, Jorg" sort="Rothe, Jorg" uniqKey="Rothe J" first="Jörg" last="Rothe">Jörg Rothe</name></country><country name="États-Unis"><region name="Kentucky"><name sortKey="Goldsmith, Judy" sort="Goldsmith, Judy" uniqKey="Goldsmith J" first="Judy" last="Goldsmith">Judy Goldsmith</name></region><name sortKey="Mattei, Nicholas" sort="Mattei, Nicholas" uniqKey="Mattei N" first="Nicholas" last="Mattei">Nicholas Mattei</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000E18 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000E18 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:1BCC5806382BABE9671E5E117FAEB15D32AF2F1E
|texte= The Complexity of Probabilistic Lobbying
}}
| This area was generated with Dilib version V0.6.31. |  |